Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

摘要

Let $P$ be a set of $n$ points and $Q$ a convex $k$-gon in ${\mathbb R}^2$.We analyze in detail the topological (or discrete) changes in the structure ofthe Voronoi diagram and the Delaunay triangulation of $P$, under the convexdistance function defined by $Q$, as the points of $P$ move along prespecifiedcontinuous trajectories. Assuming that each point of $P$ moves along analgebraic trajectory of bounded degree, we establish an upper bound of$O(k^4n\lambda_r(n))$ on the number of topological changes experienced by thediagrams throughout the motion; here $\lambda_r(n)$ is the maximum length of an$(n,r)$-Davenport-Schinzel sequence, and $r$ is a constant depending on thealgebraic degree of the motion of the points. Finally, we describe an algorithmfor efficiently maintaining the above structures, using the kinetic datastructure (KDS) framework.